package Test;

public class test1 {
    class Solution {
        public int tribonacci(int n) {
            //1.创建dp表
            //2.初始化
            //3.填表
            //4.返回值

            //处理一下边界情况
            if (n == 0) return 0;
            if (n == 1 || n == 2) return 1;
            int[] dp = new int[n + 1];
            dp[0] = 0;
            dp[1] = dp[2] = 1;
            for (int i = 3; i <= n; i++) {
                dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];

            }
            return dp[n];
        }

        class Solution1 {
            private static final int MOD = 1000000007;
            //int MOD = (int)le9 + 7
            public int waysToStep(int n) {
                if (n == 1) return 1;
                if (n == 2) return 2;
                if (n == 3) return 4;

                // 初始化动态规划数组
                int[] dp = new int[n + 1];
                dp[1] = 1;
                dp[2] = 2;
                dp[3] = 4;

                // 动态规划填表
                for (int i = 4; i <= n; i++) {
                    dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
                }

                // 返回n阶台阶的上楼梯方式数
                return dp[n];
            }

            public static void main(String[] args) {
                Solution1 solution = new Solution1();
                System.out.println(solution.waysToStep(3));
                System.out.println(solution.waysToStep(5));
            }
        }


    }
}
